Міністерство освіти і науки України
Запорізька державна інженерна академія
Кафедра програмного забезпечення автоматизованих систем
Курсова робота
З дисципліни «Об'єктно - орієнтоване програмування»
На тему: «Реалізація АВЛ - дерев через класи об'єктно - орієнтованого програмування»
Виконав: ст. гр. СП - 07 - 1З Воронько О.А.
Перевірив: Попівщій В.І.
Запоріжжя, 2009р.
ПЛАН
Введення
1. Основні терміни
2. Основні операції з АВЛ - деревами
3. Алгоритм р еалізаціі АВЛ - дерев через класи об'єктно - орієнтованого програмування
Список літератури
ВСТУП
Мова програмування С + + є одним з найбільш популярних засобів об'єктно - орієнтованого програмування, що дозволяє розробляти програми, ефективні за обсягом коду та швидкості виконання. С + + включає велику кількість операцій і типів даних, засоби управління обчислювальними процесами, механізми модифікації типів даних і методи їх обробки і, як наслідок, є потужним мовою програмування. Він дозволяє описувати процеси обробки інформації, починаючи з рівня окремих розрядів, видів і адрес пам'яті, переходячи на основі механізмів об'єктно - орієнтованого програмування до близьких конкретним предметним областям поняттями.
Перші програми для цифрових обчислювальних машин рідко перевищували обсяг 1 кбайт. Обсяги використовуваних програм і програмних систем вимірюються не тільки десятками кілобайтів, а й сотнями мегабайтів. Разом з тим питома вартість створення програм (нормована обсягом програми) до останнього часу змінювалася мало. Більше того, із зростанням обсягу програми питома вартість її створення могла нелінійно зростати. Тому не дивно, що одним з основних факторів, що визначають розвиток технології програмування, є зниження вартості проектування та створення програмних продуктів (ПП), або боротьба зі складністю програмування.
Іншими найважливішими чинниками, що впливають на еволюцію методів проектування і створення ПП, є:
зміна архітектур обчислювальних засобів (ПС) в інтересах підвищення продуктивності, надійності та комунікативності;
спрощення взаємодії користувачів з ПС та інтелектуалізація НД
Дія двох останніх чинників, як правило, пов'язане із зростанням складності програмного забезпечення НД Складність представляє невід'ємне властивість програмування і програм, яке проявляється в часі і вартості створення програм, в обсязі або довжині тексту програми, характеристики її логічної структури, що задається операторами передачі управління (розгалуження, цикли, виклики підпрограм і ін.)
Можна виділити 5 наступних джерел складності програмування:
1) вирішити завдання;
2) мова програмування;
3) середовище виконання програми;
4) технологічний процес колективної розробки і створення ПП;
5) прагнення до універсальності та ефективності алгоритмів і типів даних.
Від властивості складності не можна позбутися, але можна змінювати характеристики його прояви шляхом управління або організації.
У програмуванні широко використовується фундаментальний принцип управління складними системами, який відомий людині з глибокої давнини - devide et impera (розділяй і володарюй, лат.) і широко їм застосовується при розробці і проектуванні будь-яких складних технічних систем.
В даний час об'єктно - орієнтоване програмування (ООП) є домінуючим стилем при створенні великих програм.
1. ОСНОВНІ ТЕРМІНИ
Так історично склалося, що у цих дерев є два альтернативні назви: АВЛ - дерева і збалансовані дерева. АВЛ походить від прізвищ винахідників.
Ідеально збалансованим називається дерево, у якого для кожної вершини виконується вимога: число вершин у лівому та правому піддерева розрізняється не більше, ніж на 1. Однак ідеальну збалансованість досить важко підтримувати.
У деяких випадках при додаванні / видаленні може знадобитися значна перебудова дерева, не гарантує логарифмічною складності. Тому Г.М. Адельсон - Бєльський і Є.М. Ландіс ввели менш суворе визначення збалансованості і довели, що при такому визначенні можна написати програми додавання / видалення, що мають логарифмічну складність і зберігають дерево збалансованим.
Дерево вважається збалансованим за АВЛ (надалі просто «збалансованим»), якщо для кожної вершини виконується вимога: висота лівого і правого піддерев відрізняються не більш, ніж на 1. Не всяке збалансоване дерево ідеально збалансовано, але всяке ідеально збалансоване дерево збалансовано.
Бінарні дерева пошуку призначені для швидкого доступу до даних. В ідеалі розумно збалансоване дерево має висоту порядку O (log2n). Однак при деякому збігу обставин дерево може виявитися виродженим. Тоді висота його буде O (n), і доступ до даних істотно сповільниться. Розглянемо модифікований клас дерев, що володіють усіма перевагами бінарних дерев пошуку і ніколи не вироджуються. Вони називаються збалансованими або АВЛ - деревами. Під збалансованістю будемо розуміти те, що для кожного вузла дерева висоти обох його піддерев відрізняються не більш ніж на 1.
Строго кажучи, цей критерій потрібно називати АВЛ - збалансованістю на відміну від ідеальної збалансованості, коли для кожного вузла дерева кількості вузлів у лівому та правому піддерева відрізняються не більш ніж на 1. Тут ми завжди будемо мати на увазі АВЛ - збалансованість.
Нові методи вставки і видалення в класі АВЛ - дерев гарантують, що всі вузли залишаться збалансованими по висоті. На малюнках 1 і 2 показані еквівалентні подання масиву АВЛ - деревом і бінарним деревом пошуку. Малюнок 1 представляє простий пятіелементний масив А (A [5] = {1,2,3,4,5}), відсортований за зростанням. Малюнок 2 представляє масив B (B [8] = {20, 30, 80, 40, 10, 60, 50, 70}).
Бінарне дерево пошуку має висоту 5, в той час як висота АВЛ - дерева дорівнює 2. У загальному випадку висота збалансованого дерева не перевищує O (log2n). Таким чином, АВЛ - дерево є потужною структурою зберігання, що забезпечує швидкий доступ до даних.
Для цього використовуємо підхід, при якому пошукове дерево будується окремо від своїх вузлів. Спочатку розробляємо клас AVLTreeNode, а потім використовуємо об'єкти цього типу для конструювання класу AVLTree. Предметом пильної уваги будуть методи Insert і Delete.
Вони вимагають ретельного проектування, оскільки повинні гарантувати, що всі вузли нового дерева залишаться збалансованими по висоті.
2. ОСНОВНІ ОПЕРАЦІЇ З АВЛ - ДЕРЕВАМИ
Відновлення збалансованості.
Нехай є дерево, збалансоване всюди, крім кореня, а в корені показник збалансованості за модулем дорівнює 2 - м. Таке дерево можна збалансувати за допомогою одного з чотирьох обертань. При цьому висота дерева може зменшитися на 1. Для відновлення балансу після видалення / додавання вершини треба пройти шлях від місця видалення / додавання до кореня дерева, проводячи при необхідності перебалансировку і зміна показника збалансованості вершин вздовж шляху до кореня.
Додавання елемента в збалансований дерево.
Алгоритм вставки нового елемента в збалансований дерево буде складатися з наступних трьох основних кроків:
Пошук по дереву.
Вставка елемента в місце, де закінчився пошук, якщо елемент відсутній.
Відновлення збалансованості.
Першого та 2 - ий кроки необхідні для того, щоб переконатися у відсутності елементу в дереві, а також знайти таке місце вставки, щоб після вставки дерево залишилося впорядкованим.
Третій крок являє собою зворотний прохід по шляху пошуку: від місця додавання до кореня дерева. У міру просування по цьому шляху коригуються показники збалансованості прохідних вершин і виробляється балансування там, де це необхідно. Додавання елемента в дерево ніколи не вимагає більш одного повороту.
Ефективність сортування вставкою в АВЛ - дерево.
Очікуване число порівнянь, необхідних для вставки вузла в бінарне дерево пошуку, так само O (log2n). Оскільки в дерево вставляється n елементів, середня ефективність повинна бути O (n log2n). Однак у гіршому випадку, коли вихідний список відсортований у зворотному порядку, вона складе O (n2). Відповідне дерево пошуку вироджується в зв'язаний список. Покажемо, що найгірший випадок вимагає O (n2) порівнянь. Перша вставка вимагає 0 порівнянь. Друга вставка - двох порівнянь (одне з коренем і одне для визначення того, в який піддерево слід вставляти дане значення). Третя вставка вимагає трьох порівнянь, 4 - а чотирьох ,..., n - я вставка вимагає n порівнянь. Тоді загальна кількість порівнянь одно:
0 + 2 + 3 + ... + N = (1 + 2 + 3 + ... + n) - 1 = n (n + 1) / 2 - 1 = O (n2)
Для кожного вузла дерева пам'ять повинна виділятися динамічно, тому найгірший випадок не краще, ніж сортування обміном.
Коли n випадкових значень повторно вставляються в бінарне дерево пошуку, можна очікувати, що дерево буде відносно збалансованим. Найкращим випадком є закінчене бінарне дерево. Для цього випадку можна оцінити верхню межу, розглянувши повне дерево глибиною d. На i-му рівні (1 ≤ i ≤ d) є 2i вузлів. Оскільки для приміщення вузла на рівень i потрібно i +1 порівняння, сортування на повному дереві вимагає (i +1) * 2i порівнянь для вставки всіх елементів на рівень i.
Якщо згадати, що n = 2 (d +1) - 1, то верхня межа міри ефективності виражається наступним нерівністю:
Таким чином, ефективність алгоритму в кращому випадку складе O (n log2n).
Видалення елемента зі збалансованого дерева.
Алгоритм видалення елемента з збалансованого дерева буде виглядати так:
Пошук по дереву.
Видалення елемента з дерева.
Відновлення збалансованості дерева (зворотний прохід).
Першого та 2 - ий кроки необхідні, щоб знайти в дереві вершину, яка повинна бути вилучена.
Третій крок являє собою зворотний прохід від місця, з якого взято елемент для заміни видаляється, або від місця, з якого видалено елемент, якщо в заміні не було необхідності.
Операція видалення може зажадати перебалансування всіх вершин вздовж дороги назад до кореня дерева, тобто порядку log (N) вершин.
Аналіз операцій над збалансованим деревом.
Зрозуміло, що у разі повного двійкового дерева ми отримаємо складність T (log (n)) (на кожному кроці розмір дерева пошуку буде скорочуватися вдвічі). Розглянемо мінімальне збалансоване дерево (найгірший випадок). Таким буде дерево, у якого для кожної вершини висота лівого і правого піддерев розрізняються на 1. Для такого дерева можна записати наступну рекуррентную формулу для числа вершин (h - висота дерева):
Покажемо, що h <log 2 (N h). Для цього необхідно і достатньо показати, що 2 h> N h. Доведемо останнє методом математичної індукціі.а) h = 0: 2 0> N 0 = 0; б) h = 1: 2 1> N 1 = 1, в) h> 1: Нехай 2 h-2> N h-2 і 2 h-1> N h-1. Тоді 2 h-2 +2 h-1> N h-2 + N h-1. І далі отримуємо 2 h> 1 +2 h-2 +2 h-1> 1 + N h-2 + N h-1 = N h, що й потрібно було довести.
Таким чином алгоритми пошуку / додавання / видалення елементів у збалансованому дереві мають складність T (log (n)). Г.М. Адельсон-Бєльський і Є.М. Ландіс довели теорему, згідно якої висота збалансованого дерева ніколи не перевищить висоту ідеально збалансованого дерева більш, ніж на 45%.
Основні вузли АВЛ - дерев.
АВЛ - дерева мають структуру, схожу на бінарні дерева пошуку. Всі операції ідентичні описаним для бінарних дерев, за винятком методів Insert і Delete, які повинні постійно відслідковувати співвідношення висот лівого і правого піддерев вузла. Для збереження цієї інформації розширюємо визначення об'єкта TreeNode, включивши полі balanceFactor (показник збалансованості), яке містить різницю висот правого і лівого піддерев.
Left data balanceFactor right
AVLTreeNode
balanceFactor = height (right subtree) - height (left subtree)
Якщо balanceFactor негативний, то вузол «переважує вліво», оскільки висота лівого піддерева більше, ніж висота правого піддерева. При позитивному balanceFactor вузол «переважує вправо». Збалансований по висоті вузол має balanceFactor = 0.
У АВЛ - дереві показник збалансованості повинен бути в діапазоні [-1, 1]. На малюнку 3 зображено АВЛ - дерева з позначками -1, 0 і +1 на кожному вузлі, що показують відносний розмір лівого і правого піддерев.
-1: Висота лівого піддерева на 1 більше висоти правого піддерева.
0: Висоти обох піддерев однакові.
+1: Висота правого піддерева на 1 більше висоти лівого піддерева.
Рис. 1.
Рис. 2.
Використовуючи властивості наслідування, можна утворити клас AVLTreeNode на базі класу TreeNode. Об'єкт типу AVLTreeNode успадковує поля з класу TreeNode і додає до них полі balanceFactor. Дані - члени left і right класу TreeNode є захищеними, тому AVLTreeNode або інші похідні класи мають до них доступ.
Рис. 3.
Специфікація класу AVLTreeNode.
Оголошення:
/ / спадкоємець класу TreeNode
template <class T>
class AVLTreeNode: public TreeNode <T>
{
private:
/ / Додатковий член класу balanceFactor використовується методами класу AVLTree і дозволяє уникати "переважування" вузлів
int balanceFactor;
AVLTreeNode <T> * & Left (void);
AVLTreeNode <T> * & Right (void);
public:
/ / Конструктор
AVLTreeNode (const T & item, AVLTreeNode <T> * lptr = NULL,
AVLTreeNode <T> * rptr = NULL, int balfac = 0);
/ / Повернути лівий / правий покажчик вузла типу TreeNode перетворивши його до типу AVLTreeNode
AVLTreeNode <T> * Left (void) const;
AVLTreeNode <T> * Right (void) const;
/ / Метод для доступу до нового полю даних
int GetBalanceFactor (void);
/ / Методи класу AVLTree повинні мати доступ до Left і Right
friend class AVLTree <T>;
};
Опис:
Елемент даних balanceFactor є прихованим, так як оновлювати його повинні тільки вирівнюють баланс операції вставки та видалення. Доступ до полів - вказівниками здійснюється за допомогою методів Left і Right. Нові визначення для цих методів обов'язкові, оскільки вони повертають покажчик на структуру AVLTreeNode.
Оскільки клас AVLTree утворений на базі класу BinSTree, будемо використовувати деструктор базового класу і метод ClearList. Ці методи видаляють вузли за допомогою оператора delete. У кожному випадку покажчик посилається на об'єкт типу AVLTreeNode, а не TreeNode. Так як деструктор базового класу TreeNode віртуальний, при виклику delete використовується динамічне зв'язування і віддаляється об'єкт типу AVLTreeNode.
Приклад:
Ця функція створює АВЛ - дерево, зображене на малюнку 4. Кожному вузлу присвоюється показник збалансованості.
Рис. 4.
AVLTreeNode <char> * root; / / корінь АВЛ - дерева
void MakeAVLCharTree (AVLTreeNode <char> * & root)
{
AVLTreeNode <char> * a, * b, * c, * d, * e;
e = new AVLTreeNode <char> ('E', NULL, NULL, 0);
d = new AVLTreeNode <char> ('D', NULL, NULL, 0);
c = new AVLTreeNode <char> ('C', e, NULL, -1);
b = new AVLTreeNode <char> ('B', NULL, d, 1);
a = new AVLTreeNode <char> ('A', b, c, 0);
root = a;
}
Реалізація класу AVLTreeNode.
Конструктор класу AVLTreeNode викликає конструктор базового класу і ініціалізує balanceFactor.
/ / Конструктор ініціалізує balanceFactor і базовий клас
/ / Початкові значення полів покажчиків за замовчуванням, рівні NULL
/ / Ініціалізували вузол як лист
template <class T>
AVLTreeNode <T>:: AVLTreeNode (const T & item,
AVLTreeNode <T> * lptr, AVLTreeNode <T> * rptr, int balfac):
TreeNode <T> (item, lptr, rptr), balanceFactor (balfac)
{}
Методи Left і Right в класі AVLTreeNode спрощують доступ до полів даних. При спробі звернутися до лівого синові за допомогою методу Left базового класу повертається вказівник на об'єкт типу TreeNode. Щоб отримати покажчик на вузол АВЛ - дерева, потрібно перетворення типів.
Наприклад:
AVLTreeNode <T> * p, * q;
q = p-> Left (); / / неприпустима операція
q = (AVLTreeNode <T> *) p-> Left (); / / необхідне приведення типу
Щоб уникнути постійного перетворення типу покажчиків ми визначаємо методи Left і Right для класу AVLTreeNode, повертають покажчики на об'єкти типу AVLTreeNode.
template <class T>.
AVLTreeNode <T> * AVLTreeNode:: Left (void)
{
return ((AVLTreeNode <T> *) left;
}
Клас AVLTree.
АВЛ - дерево являє собою списковому структуру, схожу на бінарне дерево пошуку, з одним додатковим умовою: дерево має залишатися збалансованим за висотою після кожної операції вставки або видалення. Оскільки АВЛ - дерево є розширеним бінарним деревом пошуку, клас AVLTree будується на базі класу BinSTree і є його спадкоємцем.
Для виконання АВЛ - умов слід змінити методи Insert і Delete. Крім того, у похідному класі визначаються конструктор копіювання і перевантажений оператор присвоєння, так як ми будуємо дерево з більшою вузловий структурою.
Специфікація класу AVLTree.
Оголошення:
/ / Значення показника збалансованості вузла
const int leftheavy = - 1;
const int balanced = 0;
const int rightheavy = 1;
template <class T>
class AVLTree: public BinSTree <T>
{
private:
/ / Виділення пам'яті
AVLTreeNode <T> * GetAVLTreeNode (const T & item,
AVLTreeNode <T> * lptr, AVLTreeNode <T> * rptr);
/ / Використовується конструктором копіювання і оператором присвоювання
AVLTreeNode <T> * CopyTree (AVLTreeNode <T> * t);
/ / Використовується методами Insert і Delete для відновлення АВЛ - умов після операцій вставки / видалення
void SingleRotateLeft (AVLTreeNode <T> * & p);
void SingleRotateRight (AVLTreeNode <T> * & p);
void DoubleRotateLeft (AVLTreeNode <T> * & p);
void DoubleRotateRight (AVLTreeNode <T> * & p);
void UpdateLeftTree (AVLTreeNode <T> * & tree,
int & reviseBalanceFactor);
void UpdateRightTree (AVLTreeNode <T> * & tree,
int & reviseBalanceFactor);
/ / Спеціальні версії методів Insert і Delete
void AVLInsert (AVLTreeNode <T> * & tree,
AVLTreeNode <T> * newNode, int & reviseBalanceFactor);
void AVLDelete (AVLTreeNode <T> * & tree,
AVLTreeNode <T> * newNode, int & reviseBalanceFactor);
public:
/ / Конструктори
AVLTree (void);
AVLTree (const AVLTree <T> & tree);
/ / Оператор присвоювання
AVLTree <T> & operator = (const AVLTree <T> & tree);
/ / Стандартні методи обробки списків
virtual void Insert (const T & item);
virtual void Delete (const T & item);
};
Опис:
Константи leftheavy, balanced і rightheavy використовуються в операціях вставки / видалення для опису показника збалансованості вузла. Метод GetAVLTreeNode управляє виділенням пам'яті для екземпляра класу. За замовчуванням balanceFactor нового вузла дорівнює нулю.
Рис. 5.
У цьому класі заново визначається функція CopyTree для використання з конструктором копіювання і перевантаженим оператором присвоєння. Незважаючи на те, що алгоритм ідентичний алгоритму для функції CopyTree класу BinSTree, нова версія коректно створює розширені об'єкти типу AVLTreeNode при побудові нового дерева.
Функції AVLInsert і AVLDelete реалізують методи Insert і Delete, відповідно. Вони використовують приховані методи на кшталт SingleRotateLeft. Відкриті методи Insert і Delete оголошені віртуальними і підміняють відповідні функції базового класу. Інші операції успадковуються від класу BinSTree.
Приклад:
Код, наведений нижче, створює дерева, наведені на рисунку 5. Після видалення з АВЛ - дерева (В) елемента 3 АВЛ - дерево приймає вигляд, зображений на малюнку 5 (С). Цифра після двокрапки означає чинник збалансованості.
AVLTree <int> avltree; / / AVLTree - список цілих чисел
BinSTree <int> bintree; / / BinSTree - список цілих чисел
for (int i = 1; i <= 5; i + +)
{
bintree.Insert (i); / / створити дерево А
avltree.Insert (i); / / створити дерево У
}
avltree.Delete (3); / / видалити 3 з АВЛ - дерева
/ / Дерево (С) є дерево (В) без вилученого вузла 3.
Розподіл пам'яті для AVLTree.
Клас AVLTree утворений від класу BinSTree і успадковує більшість його операцій. Для створення розширених об'єктів типу AVLTreeNode ми розробили окремі методи виділення пам'яті і копіювання.
/ / Розмістити в пам'яті об'єкт типу AVLTreeNode, перервати програму якщо під час виділення пам'яті сталася помилка
template <class T>
AVLTreeNode <T> * AVLTree <T>:: GetAVLTreeNode (const T & item,
AVLTreeNode <T> * lptr, AVLTreeNode <T> * rptr)
{
AVLTreeNode <T> * p;
p = new AVLTreeNode <T> (item, lptr, rptr);
if (p == NULL)
{
cerr <<"Помилка виділення пам'яті!" <<Endl;
exit (1);
}
return p;
}
Для видалення вузлів АВЛ - дерева досить методів базового класу. Метод DeleteTree з класу BinSTree задіє віртуальний деструктор класу TreeNode.
Метод Insert класу AVLTree.
Перевага АВЛ - дерев полягає у їх збалансованості, яка підтримується відповідними алгоритмами вставки / видалення. Опишемо метод Insert для класу AVLTree. При реалізації методу Insert для запам'ятовування елемента використовується рекурсивна функція AVLInsert. Спочатку наведемо код методу Insert на С + +, а потім зосередимо увагу на рекурсивному методі AVLInsert, реализующем алгоритм Адельсона - Бєльського і Ландіса.
template <class T>
void AVLTree <T>:: Insert (const T & item)
{
/ / Оголосити покажчик АВЛ - дерева, використовуючи метод базового класу GetRoot
/ / Справити приведення типів для покажчиків
AVLTreeNode <T> * treeRoot = (AVLTreeNode <T> *) GetRoot (),
* NewNode;
/ / Прапор, який використовується функцією AVLInsert для перебалансування вузлів
int reviseBalanceFactor = 0;
/ / Створити новий вузол АВЛ - дерева з нульовими полями покажчиків
newNode = GetAVLTreeNode (item, NULL, NULL);
/ / Викликати рекурсивну процедуру для фактичної вставки елемента
AVLInsert (treeRoot, newNode, reviseBalancefactor);
/ / Присвоїти нові значення елементів даних базового класу
root = treeRoot;
current = newNode;
size + +;
}
Ядром алгоритму вставки є рекурсивний метод AVLInsert. Як і його аналог у класі BinSTree, цей метод здійснює проходження лівого піддерева, якщо item менше цього сайту, або правого піддерева, якщо item більше або дорівнює даному вузлу. При скануванні лівого чи правого піддерева деякого вузла аналізується прапор revisebalanceFactor, який є ознакою зміни будь-якого параметра balanceFactor в піддереві. Якщо він встановлений, то потрібно перевірити, чи збереглася АВЛ - збалансованість всього дерева.
Якщо в результаті вставки нового вузла вона виявилася порушеною, то ми зобов'язані відновити рівновагу.
Алгоритм АВЛ - вставки
Процес вставки майже такий же, що і для бінарного дерева пошуку. Здійснюється рекурсивний спуск по лівим і правим синам, поки не зустрінеться пусте піддерево, а потім проводиться пробна вставка нового вузла в цьому місці. Протягом цього процесу ми відвідуємо кожен вузол на шляху пошуку від кореневого до нового елементу. Оскільки процес рекурсивний, обробка вузлів ведеться у зворотному порядку. При цьому показник збалансованості батьківського вузла можна скорегувати після вивчення ефекту від додавання нового елемента в одне з піддерев. Необхідність коригування визначається для кожного вузла, що входить в пошуковий маршрут. Є три можливих ситуації. У двох перших випадках вузол зберігає збалансованість і реорганізація піддерев не потрібно. Потрібно лише скорегувати показник збалансованості даного вузла. У третьому випадку розбалансування дерева вимагає одинарного або подвійного поворотів вузлів.
Випадок 1. Вузол на пошуковому маршруті від початку є збалансованим (balanceFactor = 0). Після вставки в піддерево нового елемента вузол став переважувати вліво або вправо в залежності від того, в який піддерево була зроблена вставка.
Якщо елемент вставлений в ліве піддерево, показником збалансованості присвоюється -1, а якщо в праве, то 1. Наприклад, на шляху 40 - 50 - 60 кожен вузол збалансований. Після вставки вузла 55 показники збалансованості змінюються (рис. 6).
Рис. 6.
Випадок 2. Одне з піддерев вузла переважує, і новий вузол вставляється в більш легке піддерево. Вузол стає збалансованим. Порівняйте, наприклад, стану дерева до і після вставки вузла 55 (рис. 7).
Випадок 3. Одне з піддерев вузла переважує, і новий вузол поміщається в більш важке піддерево. Тим самим порушується умова збалансованості, так як balanceFactor виходить за межі -1 .. 1. Щоб відновити рівновагу, потрібно виконати поворот.
Рис. 7.
Розглянемо приклад:
Припустимо, що дерево розбалансувалася зліва і ми відновлюємо рівновагу, викликаючи одну з функцій повороту праворуч. Розбалансування праворуч тягне за собою симетричні дії. Сказане ілюструється рисунком 8.
Метод AVLInsert.
Просуваючись вздовж деякого шляхи для вставки нового вузла, рекурсивний метод AVLInsert розпізнає всі три зазначених вище випадку коригування. При порушенні умови збалансованості відновлення рівноваги здійснюється за допомогою функцій UpdateLeftTree і UpdateRightTree.
template <class T>
void AVLTree <T>:: AVLInsert (AVLTreeNode <T> * & tree,
AVLTreeNode <T> * newNode, int & reviseBalanceFactor)
{
/ / Прапор "Показник збалансованості був змінений"
int rebalanceCurrNode;
/ / Зустрілося пусте піддерево, пора вставляти новий вузол
if (tree == NULL)
{
/ / Вставити новий вузол
tree = newNode;
/ / Оголосити новий вузол збалансованим
tree-> balanceFactor = balanced;
/ / Повідомити про зміну показника збалансованості
reviseBalanceFactor = 1;
}
/ / Рекурсивно спускатися по лівому піддерево, якщо новий вузол менше поточного
else if (newNode-> data <tree-> data)
{
AVLInsert (tree-> Left (), newNode, rebalanceCurrNode);
/ / Перевірити, чи потрібно коригувати balanceFactor
if (rebalanceCurrNode)
{
/ / Вставка ліворуч від вузла, переважує вліво. буде порушено
/ / Умова збалансованості; виконати поворот (випадок 3)
if (tree-> balanceFactor == leftheavy)
UpdateLeftTree (tree, reviseBalanceFactor);
/ / Вставка ліворуч від збалансованого вузла.
/ / Вузол стане переважувати вліво (випадок 1)
else if (tree-> balanceFactor == balanced)
{
tree-> balanceFactor = leftheavy;
reviseBalanceFactor = 1;
}
/ / Вставка зліва від вузла, переважує вправо
/ / Вузол стане збалансованим (випадок 2)
else
{
tree-> balanceFactor = balanced;
reviseBalanceFactor = 0;
}
}
Else
/ / Перебалансування не потрібно. не опитували попередні вузли
reviseBalanceFactor = 0;
}
/ / Інакше рекурсивно спускатися по правому піддерево
else if (newNode-> data <tree-> data)
{
AVLInsert (tree-> Right (), newNode, rebalanceCurrNode);
/ / Перевірити, чи потрібно коригувати balanceFactor
if (rebalanceCurrNode)
{
/ / Вставка праворуч від вузла, переважує вправо. буде порушено
/ / Умова збалансованості; виконати поворот (випадок 3)
if (tree-> balanceFactor == rightheavy)
UpdateRightTree (tree, reviseBalanceFactor);
/ / Вставка праворуч від збалансованого вузла
/ / Вузол стане переважувати вправо (випадок 1)
else if (tree-> balanceFactor == balanced)
{
tree-> balanceFactor = rightheavy;
reviseBalanceFactor = 1;
}
/ / Вставка праворуч від вузла, переважує вліво
/ / Вузол стане збалансованим (випадок 2)
else
{
tree-> balanceFactor = balanced;
reviseBalanceFactor = 0;
}
}
else
/ / Перебалансування не потрібно. не опитували попередні вузли
reviseBalanceFactor = 0;
}
Рис. 8.
Метод AVLInsert розпізнає випадок 3, коли порушується АВЛ - умова. Для виконання перебалансування використовуються методи UpdateLeftTree і UpdateRightTree. Вони виконують одинарний або подвійний поворот для врівноваження вузла, а потім скидають прапор reviseBalanceFactor. Перед тим, як обговорити специфічні деталі поворотів, наведемо код функції UpdateLeftTree.
template <class T>
void AVLTree <T>:: UpdateLeftTree (AVLTreeNode <T> * & p,
int reviseBalanceFactor)
{
AVLTreeNode <T> * lc;
lc = p-> Left ();
/ / Переважує ліве піддерево?
if (lc-> balanceFactor == leftheavy)
{
SingleRotateRight (p); / / одноразовий поворот
reviseBalanceFactor = 0;
}
/ / Переважує праве піддерево?
else if (lc-> balanceFactor == rightheavy)
{
/ / Виконати подвійний поворот
DoubleRotateRight (p);
/ / Тепер корінь урівноважений
reviseBalanceFactor = 0;
}
Обертання (Повороти) АВЛ - дерев.
При операціях додавання і видалення може відбутися порушення збалансованості дерева. У цьому випадку будуть потрібні деякі перетворення, що не порушують впорядкованості дерева і сприяють кращій збалансованості.
Розглянемо такі перетворення.
У кожній вершині дерева крім значення елемента будемо зберігати показник збалансованості в даній вершині. Показник збалансованості - різниця між висотами правого і лівого піддерев.
PTree = ^ TTree;
TTree = record
Item: T; {елемент дерева}
Left, Right: PTree; {покажчики на піддерева}
Balance: ShortInt; {показник збалансованості}
end;
У збалансованому дереві показники збалансованості всіх вершин лежать в межах від -1 до 1. При операціях додавання / видалення можуть з'являтися вершини з показниками збалансованості -2 і 2.
Мале ліве обертання.
Нехай показник збалансованості вершини, в якій відбулося порушення балансу, дорівнює -2, а показник збалансованості кореня лівого піддерева дорівнює -1. Тоді відновити збалансованість такого піддереві можна таким перетворенням, званим малим лівим обертанням (рис. 9.):
Рис. 9.
На наведеному малюнку прямокутниками позначені піддерева. Поруч з піддеревами вказана їх висота. Піддерева позначені арабськими цифрами. Кружечками позначені вершини. Цифра поруч з вершиною - показник збалансованості в даній вершині. Буква всередині гуртка - умовне позначення вершини. Як видно з малюнка після малого лівого обертання показник збалансованості вершини, в якій було порушення балансу, стає рівним нулю.
Мале праве обертання.
У випадку, коли показник збалансованості вершини, в якій відбулося порушення балансу, дорівнює 2, а показник збалансованості кореня правого піддерева дорівнює 1, відновити збалансованість у вершині можна за допомогою перетворення, званого малим правим обертанням. Це обертання симетрично малому лівому і схематично зображено на малюнку 10:
Рис. 10.
Велике ліве обертання.
Дещо складніше випадок, коли показник збалансованості у вершині, в якій відбулося порушення балансу дорівнює -2, а показник збалансованості в корені лівого піддерева дорівнює 1 або 0. У цьому випадку застосовується перетворення, зване великим лівим обертанням. Як видно з малюнка 11 тут в обертанні беруть участь три вершини, а не дві як у випадку малих обертань.
Рис. 11.
Велике праве обертання.
Велике праве обертання застосовується, коли показник збалансованості вершини, в якій відбулося порушення балансу, дорівнює 2, а показник збалансованості кореня правого піддерева дорівнює -1 або 0. Велике праве обертання симетрично великим лівому і схематично зображено на малюнку 12:
Рис. 12.
Повороти необхідні, коли батьківський вузол P стає розбалансованим. Одинарний поворот праворуч (single right rotation) відбувається тоді, коли батьківський вузол P і його лівий син LC починають переважувати вліво після вставки вузла в позицію X. У результаті такого повороту LC заміщає свого батька, який стає правим сином. Колишнє праве піддерево вузла LC (ST) приєднується до P як лівого піддерева. Це зберігає впорядкованість, так як вузли в ST більше або дорівнювати вузлу LC, але менше вузла P. Поворот врівноважує як батька, так і його лівого сина (рис. 13).
/ / Виконати поворот за годинниковою стрілкою навколо вузла p
/ / Зробити lc новою точкою обертання
template <class T>
void AVLTree <T>:: SingleRotateRight (AVLTreeNode <T> * & p)
{
/ / Ліве, переважує піддерево вузла p
AVLTreeNode <T> * lc;
/ / Призначити lc лівим піддерево
lc = p-> Left ();
/ / Скоригувати показник збалансованості для батьківського вузла та його лівого сина
p-> balanceFactor = balanced;
lc-> balanceFactor = balanced;
/ / Праве піддерево вузла lc в будь-якому випадку повинно залишатися праворуч від lc, виконати цю умову, зробивши st лівим піддерево вузла p
p-> Left () = lc-> Right ();
/ / Перенести p в праве піддерево вузла lc
/ / Зробити lc новою точкою обертання
lc -> Right () = p;
p = lc;
}
Рис. 13
Рис. 14.
Спроба вставити вузол 5 у зображене на малюнку 14 АВЛ - дерево порушує АВЛ - умова для вузла 30. Одночасно ліве піддерево вузла 15 (LC) стає переобтяженим.
Для переупорядоченія вузлів викликається процедура SingleRotateRight. У результаті батьківський вузол (30) стає збалансованим, а вузол 10 переважують вліво. Подвійний поворот праворуч (double right rotation) потрібен тоді, коли батьківський вузол (P) стає переважують вліво, а його лівий син (LC) переважують вправо. NP - корінь правого переважує піддерева вузла LC. Тоді в результаті повороту вузол NP заміщає батьківський вузол. На малюнках 15 і 16 показані випадки вставки нового вузла в якості сина вузла NP. В обох випадках NP стає батьківським вузлом, а колишній батько P стає правим сином NP.
На малюнку 15 ми бачимо зрушення вузла X1, після того як він був вставлений в ліве піддерево вузла NP. На малюнку 16 зображено переміщення вузла X2 після його вставки в праве піддерево NP.
Рис. 15.
Рис. 16
/ / Подвійний поворот вправо навколо вузла p
template <class T>
void AVLTree <T>:: DoubleRotateRight (AVLTreeNode <T> * & p)
{
/ / Два піддерева, що підлягають повороту
AVLTreeNode <T> * lc, * np;
/ / Вузол lc <= вузол np <вузол p
lc = p-> Left (); / / лівий син вузла p
np = lc-> Right (); / / правий син вузла lc
/ / Оновити показники збалансованості у вузлах p, lc і np
if (np-> balanceFactor == rightheavy)
{
p-> balanceFactor = balanced;
lc-> balanceFactor = rightheavy;
}
else
{
p-> balanceFactor = rightheavy;
lc-> balanceFactor = balanced;
}
np-> balanceFactor = balanced;
/ / Перед тим як замінити батьківський вузол p, слід від'єднати його від старих дітей і приєднати до нових
lc-> Right () = np-> Left ();
np-> Left () = lc;
p-> Left () = np-> Right ();
np-> Right () = p;
p = np;
}
Подвійний поворот ілюструється на дереві, зображеному на малюнку 17. Спроба вставити вузол 25 розбалансує кореневий вузол 50. У цьому випадку вузол 20 (LC) набуває дуже високий праве піддерево і потрібно подвійний поворот.
Новим батьківським вузлом (NP) стає вузол 40. Старий батьківський вузол стає його правим сином і приєднує до себе вузол 45, який також переходить з лівого боку дерева.
Рис. 17.
Оцінка збалансованих АВЛ - дерев.
Обгрунтованість застосування АВЛ - дерев неоднозначна, оскільки вони вимагають додаткових витрат на підтримку збалансованості при вставці або видаленні вузлів. Якщо в дереві постійно відбуваються вставки і видалення елементів, ці операції можуть значно знизити швидкодію.
З іншого боку, якщо ваші дані перетворюють бінарне дерево пошуку в вироджені, ви втрачаєте пошукову ефективність і змушені використовувати АВЛ - дерево. У більшості випадків у програмах використовуються алгоритми, коли спочатку заповнюється список, а потім проводиться пошук за цим списком з невеликою кількістю змін. Тому на практиці використання АВЛ - дерев переважно.
Для АВЛ - дерева не існує найгіршого випадку, так як воно є майже повним бінарним деревом. Складність операції пошуку складає O (log2n). Досвід показує, що повороти потрібні приблизно в половині випадків вставок і вилучень. Складність балансування обумовлює застосування АВЛ - дерев тільки там, де пошук є домінуючою операцією.
Оцінка продуктивності АВЛ - дерев.
Ця програма порівнює збалансоване і звичайне бінарні дерева пошуку, кожне з яких містить N випадкових чисел. Вихідні дані для цих дерев беруться з єдиного масиву. Для кожного елемента масиву здійснюється його пошук в обох деревах. Довжини пошукових шляхів підсумовуються, а потім підраховується середня довжина пошуку по кожному дереву. Програма проганяється на 1000 - і на 10000-елементному масивах.
Зверніть увагу, що на випадкових даних пошукові характеристики АВЛ - дерева дещо краще. У самому гіршому випадку вироджені дерево пошуку, що містить 1000 елементів, має середню глибину 500, в той час як середня глибина АВЛ - дерева завжди дорівнює 9.
# Include <iostream.h>
# Include "bstree.h"
# Include "avltree.h"
# Include "random.h"
/ / Завантажити з масиву числа в бінарне пошукове дерево і АВЛ - дерево
void SetupLists (BinSTree <int> & Tree1, AVLTree <int> & Tree2, int A [], int n)
{
int i;
RandomNumber rnd;
/ / Запам'ятати випадкове число в масиві А, а також вставити його в бінарне дерево пошуку і в АВЛ - дерево
for (i = 0; i <n; i + +)
{
A [i] = rnd.Random (1000);
Tree1.Insert (A [i]);
Tree2.Insert (A [i]);
}
/ / Пошук елемента item в дереві t
/ / При цьому накопичується сумарна довжина пошуку
template <class T>
void PathLength (TreeNode <T> * t, long & totallength, int item)
{
/ / Повернення, якщо елемент знайдено або відсутній у списку
if (t == NULL | | t-> data == item)
return;
else
{
/ / Перейти на наступний рівень, збільшити сумарну довжину шляху пошуку
totallength + +;
if (item <t-> data)
PathLength (t-> Left (), totallength, item);
else
PathLength (t-> Right (), totallength, item);
}
void main (void);
{
/ / Змінні для дерев і масиву
BinSTree <int> binTree;
AVLTree <int> avlTree;
int * A;
/ / Сумарні довжини пошукових шляхів елементів масиву в бінарному дереві пошуку і в АВЛ - дереві
long totalLengthBintree = 0, totalLengthAVLTree = 0;
int n, i;
cout <<"Скільки вузлів на дереві?";
cin>> n;
/ / Завантажити випадковими числами масив і обидва дерева
SetupLists (binTree, avlTree, A, n);
for (i = 0; i <n; i + +)
{
PathLength (binTree.GetRoot (), totalLengthBintree, A [i]);
PathLength ((TreeNode <int> *) avlTree.getRoot (),
totalLengthAVLTree, A [i]);
}
cout <<"Середня довжина пошуку для бінарного дерева ="
<<Float (totalLengthBintree) / n <<endl;
cout <<"Середня довжина пошуку для збалансованого дерева ="
<<Float (totalLengthAVLTree) / n <<endl;
}
Прогін 1: Скільки вузлів на дереві? 1000
Середня довжина пошуку для бінарного дерева = 10.256.
Середня довжина пошуку для збалансованого дерева = 7.901.
Прогін 2: Скільки вузлів на дереві? 10000
Середня довжина пошуку для бінарного дерева = 12.2822.
Середня довжина пошуку для збалансованого дерева = 8.5632.
Ітератори АВЛ - дерев.
Сканування вузлів дерева більш складно, ніж сканування масивів і послідовних списків, тому що дерево є нелінійною структурою і існує декілька способів проходження дерева. Проблема кожного з них полягає в тому, що до завершення рекурсивного процесу з нього неможливо вийти. Не можна зупинити сканування, перевірити вміст сайту, виконати будь-які операції з даними, а потім знову продовжити сканування з наступного вузла дерева.
Використовуючи ж ітератор, клієнт отримує засіб сканування вузлів дерева, як якщо б вони представляли собою лінійний список, без обтяжливих деталей алгоритмів проходження, що лежать в основі процесу. Наш клас використовує клас Stack і успадковується від базового класу ітератора. Тому спочатку опишемо клас Stack і базовий клас ітератора.
Специфікація класу Stack.
Оголошення:
# Include <iostreani.h>
# Include <stdlib.h>
const int MaxStackSize = 50;
class Stack
{
private:
DataType stacklist [MaxStackSize];
int top;
public:
/ / Конструктор; ініціалізує вершину
Stack (void);
/ / Операції модифікації стека
void Push (const DataType & item);
DataType Pop (void);
void ClearStack (void);
/ / Доступ до стеку
DataType Peek (void) const;
/ / Методи перевірки стану стека
int StackEmpty (void) const;
int StackFull (void) const; / / для реалізації, заснованої на масиві
};
Опис:
Дані в стеку мають тип DataType, який повинен визначатися з використанням оператора typedef. Користувач повинен перевіряти, повний чи стек, перед спробою помістити в нього елемент і перевіряти, чи не порожній чи стек, перед витяганням даних з нього. Якщо передумови для операції push або pop не задовольняються, друкується повідомлення про помилку і програма завершується. StackEmpty повертає TRUE, якщо стек порожній, і FALSE - у противному випадку. Використовуйте StackEmpty, щоб визначити, чи може виконуватися операція Pop.
StackFull повертає TRUE, якщо стек повний, і FALSE - у противному випадку. Використовуйте StackFull, щоб визначити, чи може виконуватися операція Push. ClearStack робить стек порожнім, встановлюючи top = -1. Цей метод дозволяє використовувати стек для інших цілей.
Реалізація класу Stack.
Конструктор Stack присвоює індексом top значення -1, що еквівалентно умові порожнього стека.
/ / Ініціалізація вершини стека
Stack:: Stack (void): top (- l)
{}
Операції стека.
Дві основні операції стека вставляють (Push) і видаляють (Pop) елемент з стека. Клас містить функцію Peek, що дозволяє отримувати дані елемента, що знаходиться у вершині стека, не видаляючи насправді цей елемент. При приміщенні елемента в стек, top збільшується на 1, і новий елемент вставляється в кінець масиву stacklist. Спроба додати елемент у повний стек призведе до повідомлення про помилку та завершення програми.
/ / Помістити елемент в стек
void Stack:: Push (const DataTypes item)
{
/ / Якщо стек повний, завершити виконання програми
if (top == MaxStackSize-1)
{
cerr <<"Переповнення стека! "<<endl;
exit (l);
}
/ / Збільшити індекс top і копіювати item в масив stacklist
top + +;
stacklist [top] = item;
}
Операція Pop витягує елемент із стека, копіюючи спочатку значення з вершини стека в локальну змінну temp і потім збільшуючи top на 1. Змінна temp стає повертається значенням. Спроба отримати елемент з пустого стека призводить до повідомлення про помилку та завершення програми.
/ / Взяти елемент із стека
DataType Stack:: Pop (void)
DataType temp;
/ / Стек порожній, завершити програму
if (top == -1)
{
cerr <<"Спроба звернення до порожнього стеку!" <<end.1;
exit (1);
}
/ / Вважати елемент у вершині стека
temp = stacklist [top];
/ / Зменшити top і повернути значення з вершини стека
top -;
return temp;
}
Операція Peek в основному дублює визначення Pop з єдиним важливим винятком. Індекс top не зменшується, залишаючи стек недоторканим.
/ / Повернути дані у вершині стека
DataType Stack:: Peek (void) const
{
/ / Якщо стек порожній, завершити програму
if (top == -1)
{
cerr <<"Спроба вважати дані з порожнього стека!" <<end.1;
exit (l);
}
return stacklist [top];
}
Умови тестування стека.
Під час свого виконання операції стека завершують програму при спробах клієнта звертатися до стека неправильно; наприклад, коли ми намагаємося виконати операцію Peek над порожнім стеком. Для захисту цілісності стека клас передбачає операції тестування стану стека. Функція StackEmpty перевіряє, чи є top рівним -1. Якщо - так, стек порожній і повертається значення - TRUE; інакше повертається значення - FALSE.
/ / Тестування стека на наявність у ньому даних
int Stack:: StackEmpty (void) const
{
return top == -1;
}
Функція StackFull перевіряє, чи дорівнює top значенням MaxStackSize - 1. Якщо так, то стек заповнений і повертається значенням буде TRUE; інакше, повертається значення - FALSE.
/ / Перевірка, чи не переповнений стек
int Stack:: StackFuli (void) const
{
return top == MaxStackSize -1;
}
Метод ClearStack перевстановлюємо вершину стека на -1. Це відновлює початкове умова, визначена конструктором.
/ / Видалити всі елементи з стека
void Stack:: ClearStack (void)
{
top = -1;
}
Стекові операції Push і Pop використовують прямий доступ до вершини стека і не залежать від кількості елементів у списку.
Абстрактний базовий клас Iterator.
Клас Iterator дозволяє абстрагуватися від тонкощів реалізації алгоритму перебору, що дає незалежність від деталей реалізації базового класу. Ми визначаємо абстрактний клас Iterator як шаблон для ітераторів списків загального вигляду.
Специфікація класу Iterator.
Оголошення:
template <class T>
class Iterator
{
protected:
/ / Прапор, який показує, чи досяг ітератор кінця списку повинен підтримуватися похідними класами
int iterationComplete;
public:
/ / Конструктор
Iterator (void);
/ / Обов'язкові методи ітератора
virtual void Next (void) = 0;
virtual void Reset (void) = 0;
/ / Методи для вибірки / модифікації даних
virtual T & Data (void) = 0;
/ / Перевірка кінця списку
virtual int EndOfList (void) const;
};
Обговорення:
Ітератор є засобом проходження списку. Його основні методи: Reset (установка на перший елемент списку), Next (перехід на наступний елемент), EndOfList (визначення кінця списку). Функція Data здійснює доступ до даних поточного елемента списку.
Ітератор симетричного методу проходження.
Симетричне проходження бінарного дерева пошуку, в процесі якого вузли відвідуються в порядку зростання їх значень, є корисним інструментом.
Оголошення:
/ / Ітератор симетричного проходження бінарного дерева використовує базовий клас Iterator
template <class T>
class InorderIterator: public Iterator <T>
{
private:
/ / Підтримувати стек адрес вузлів
Stack <TreeNode <T> *> S;
/ / Корінь дерева і поточний вузол
TreeNode <T> * root, * current;
/ / Сканування лівого піддерева використовується функцією Next
TreeNode <T> * GoFarLeft (TreeNode <T> * t);
public:
/ / Конструктор
InorderIterator (TreeNode <T> * tree);
/ / Реалізації базових операцій проходження
virtual void Next (void);
virtual void Reset (void);
virtual T & Data (void);
/ / Призначення ітератора нового дерева
void SetTree (TreeNode <T> * tree);
};
Опис:
Клас InorderIterator побудований за загальним для всіх ітераціях зразком. Метод EndOfList визначений в базовому класі Iterator. Конструктор ініціалізує базовий клас і з допомогою GoFarLeft знаходить початковий вузол сканування.
Приклад:
TreeNode <int> * root; / / бінарне дерево
InorderIterator treeiter (root); / / приєднати ітератор
/ / Роздрукувати початковий вузол сканування для змішаного проходження це самий лівий вузол дерева
cout <<treeiter.Data ();
/ / Сканування вузлів і друк їх значень
for (treeiter.Reset ();! treeiter.EndOfList (); treeiter.Next ())
cout <<treeiter.Data () <<"";
Реалізація класу InorderIterator.
Ітераційний симетричний метод проходження емулює рекурсивне сканування за допомогою стека адрес вузлів. Починаючи з кореня, здійснюється спуск вздовж лівих піддерев. По дорозі покажчик кожного пройденого вузла запам'ятовується в стеку. Процес зупиняється на вузлі з нульовим лівим покажчиком, який стає першим відвідуваним вузлом у симетричному скануванні. Спуск від вузла t і запам'ятовування адрес вузлів у стеку виконує метод GoFarLeft. Викликом цього методу з t = root шукається перший відвідуваний вузол (рис. 18).
/ / Повернути адресу крайнього вузла на лівій гілки вузла t
/ / Запам'ятати в стеку адреси всіх пройдених вузлів
template <class T>
TreeNode <T> * InorderIterator <T>:: GoFArLeft (TreeNode <T> * t)
{
/ / Якщо t = NULL, повернути NULL
if (t == NULL)
return NULL;
/ / Поки не зустрінеться вузол з нульовим лівим покажчиком, спускатися по лівим гілкам, запам'ятовуючи в стеку S адреси пройдених вузлів. Повернути покажчик на цей вузол
while (t -> Left ()! = NULL)
{
S. Push (t);
t = t-> Left ();
}
return t;
}
Рис. 18.
Після ініціалізації базового класу конструктор присвоює елементу даних root адресу кореня бінарного дерева пошуку. Вузол для початку симетричного сканування виходить в результаті виклику функції GoFarLeft з root як параметр. Це значення запам'ятовується у змінній сurrent.
/ / Ініціалізувати прапор iterationComplete. Базовий клас скидає його, але
/ / Дерево може бути порожнім. початковий узлел сканування - крайній зліва вузол.
template <class T>
InorderIterator <T>:: InorderIterator (TreeNode <T> * tree):
Iterator <T> (), root (tree)
{
iterationComplete = (root == NULL);
current = GoFarLeft (root);
}
Метод Reset по суті є таким же, як і конструктор, за винятком того, що він очищає стек. Перед першим зверненням до Next покажчик current вже вказує на перший вузол симетричного сканування. Метод Next працює за наступним алгоритмом. Якщо права гілка вузла не порожня, перейти до його правого сина і здійснити спуск по лівим гілкам до вузла з нульовим лівим покажчиком, попутно запам'ятовуючи в стеку адреси пройдених вузлів.
Якщо права гілка вузла порожня, то сканування його лівої галузі, самого вузла і його правої гілки завершено. Адреса наступного вузла, що підлягає обробці, знаходиться в стеку. Якщо стік не порожній, вилучити наступний вузол. Якщо ж стек порожній, то всі вузли оброблені і сканування завершено. Ітераційне проходження дерева, що складається з п'яти вузлів, зображено на малюнку 19.
Рис. 19.
template <class T>
void InorderIterator <T>:: Next (void)
{
/ / Помилка, якщо всі вузли вже відвідувалися
if (iterationComplete)
{
cerr <<"Next: ітератор пройшов кінець списку! "<<endl;
exit (1);
}
/ / Current - поточний оброблюваний вузол
/ / Якщо є праве піддерево, спуститися до кінця за його лівої галузі, попутно запам'ятовуючи в стеку адреси пройдених вузлів
if (current-> Right ()! = NULL)
current = GoFarLeft (current-> Right ());
/ / Правого піддерева немає, але в стеку є інші вузли, що підлягають обробці.
/ / Виштовхнути з стека новий поточний адресу, просунутися вгору по дереву
else if (! S. StackEmpty ())
current = S. Pop ();
/ / Немає ні правого піддерева, ні вузлів у стеці. Сканування завершено
else
iterationComplete = 1;
}
Алгоритм TreeSort.
Коли об'єкт типу InorderIterator здійснює проходження дерева пошуку, вузли проходяться в сортованого порядку і, отже, можна побудувати ще один алгоритм сортування, званий TreeSort. Цей алгоритм передбачає, що елементи спочатку зберігаються в масиві. Пошукове дерево служить фільтром, куди елементи масиву копіюються у відповідності з алгоритмом вставки в бінарне дерево пошуку. Здійснюючи симетричне проходження цього дерева і записуючи елементи знову в масив, ми отримуємо в результаті відсортований список. На малюнку 20 показано сортування 8 - елементного масиву.
# Include "bstree.h"
# Include "treeiter.h"
/ / Використання бінарного дерева пошуку для сортування масиву
template <class T>
void TreeSort (T arr [], int n)
{
/ / Бінарне дерево пошуку, в яке копіюється масив
BinSTree <T> sortTree;
int i;
/ / Вставити кожен елемент масиву в пошукове дерево
for (i = 0; i <n; i + +)
sortTree.Insert (arr [i]);
/ / Оголосити ітератор симетричного проходження для sortTree
InorderIterator <T> treeSortIter (sortTree.GetRoot ());
/ / Виконати симетричне проходження дерева
/ / Скопіювати кожен елемент знову в масив
i = 0;
while (! treeSortIter.EndOfList ())
{
arr [i + +] = treeSortIter.Data ();
treeSortIter.Next ();
}
}
Рис. 20.
3. Алгоритм р еалізаціі АВЛ - дерев через класи об'єктно - орієнтованого програмування.
Програма створена на об'єктно - орієнтованої мови програмування C + + в середовищі швидкої розробки (RAD) Bolrand C + + Builder 6.0, має графічний інтерфейс.
Текст програми.
# Pragma once
template <typename KEY,typename VALUE> class AvlTree
{
public:
KEY key;
VALUE value;
int balance;
AvlTree <KEY, VALUE> * left;
AvlTree <KEY, VALUE> * right;
bool empty; / / заповнені ключ і значення чи ні
AvlTree ()
{
empty = true;
left = NULL;
right = NULL;
balance = 0;
}
AvlTree (KEY Key, VALUE Value)
{
empty = false;
key = Key;
value = Value;
left = NULL;
right = NULL;
balance = 0;
}
int add (KEY Key, VALUE Value) / / додавання вузла, повертає змінився баланс (1) чи ні (0)
{/ / При додаванні в праву гілку баланс вузла збільшую на результат додавання
if (empty) / / в ліву зменшую
{/ / Після кожного виклику add (...) викликаю TurnAround ();
key = Key; / / дерево перебудовується поки нащадок поточного вузла в потрібному напрямку не буде NULL
value = Value; / / потім у цього нащадка записуємо нові значення
empty = false;
return 0;
}
if (Key == key)
throw CString (L "Вже є ");
int a = balance;
if (Key> key)
{
if (right! = NULL)
{
balance + = right-> add (Key, Value);
TurnAround ();
}
else
{
right = new AvlTree <KEY, VALUE> (Key, Value);
balance + +;
}
}
else
{
if (left! = NULL)
{
balance -= left-> add (Key, Value);
TurnAround ();
}
else
{
left = new AvlTree <KEY, VALUE> (Key, Value);
balance -;
}
}
if (balance! = a)
{
return 1;
}
else
{
return 0;
}
}
void TurnAround () / / нормалізація дерева, якщо баланс не рівномірний зміщуються (повертаю) вузол так,
{/ / Щоб кількість нащадків справа і зліва не відрізнялося більше, ніж на 1
if (balance == 2)
{
if (right-> balance> = 0)
{
KEY tKey = key;
VALUE tValue = value;
key = right-> key;
value = right-> value;
right-> key = tKey;
right-> value = tValue;
AvlTree <KEY, VALUE> * tNode = right-> right;
right-> right = right-> left;
right-> left = left;
left = right;
right = tNode;
balance = left-> balance - 1;
left-> balance = 1 - left-> balance;
}
else
{
KEY tKey = key;
VALUE tValue = value;
key = right-> left-> key;
value = right-> left-> value;
right-> left-> key = tKey;
right-> left-> value = tValue;
AvlTree <KEY, VALUE> * tNode = right-> left-> right;
right-> left-> right = right-> left-> left;
right-> left-> left = left;
left = right-> left;
right-> left = tNode;
balance = 0;
right-> balance = (left-> balance == -1)? (1): (0);
left-> balance = (left-> balance == 1)? (-1): (0);
}
}
else
{
if (balance == -2)
{
if (left-> balance <= 0)
{
KEY tKey = key;
VALUE tValue = value;
key = left-> key;
value = left-> value;
left-> key = tKey;
left-> value = tValue;
AvlTree <KEY, VALUE> * tNode = left-> left;
left-> left = left-> right;
left-> right = right;
right = left;
left = tNode;
balance = 1 + right-> balance;
right-> balance = -1 - right-> balance;
}
else
{
KEY tKey = key;
VALUE tValue = value;
key = left-> right-> key;
value = left-> right-> value;
left-> right-> key = tKey;
left-> right-> value = tValue;
AvlTree <KEY, VALUE> * tNode = left-> right-> left;
left-> right-> left = left-> right-> right;
left-> right-> right = right;
right = left-> right;
left-> right = tNode;
balance = 0;
left-> balance = (right-> balance == 1)? (-1): (0);
right-> balance = (right-> balance == -1)? (1): (0);
}
}
}
}
typename AvlTree <KEY, VALUE> * getNode (KEY Key) / / пошук вузла по ключу
{
AvlTree <KEY, VALUE> * node = this;
while (true)
{
if (node == NULL)
throw CString (L "Не знайдено ");
if (node-> key == Key)
return node;
if (node-> key <Key)
{
node = node-> right;
}
else
{
node = node-> left;
}
}
}
int remove (KEY Key, AvlTree <KEY, VALUE> * parent = NULL) / / видалення вузла, переміщаюся по дереву, по ключу
{/ / При проходженні вузла знову міняю баланс в залежності від напрямку і повертаю його TurnAround ()
int a = balance; / / як дійшов до потрібного вузла переміщаю його, поки обидва його нащадка не будуть NULL
if (key == Key) / / і видаляю
{
if (right == NULL & & left == NULL)
{
if (parent-> left-> key == this-> key)
{
parent-> left = NULL;
}
else
{
parent-> right = NULL;
}
return 1;
}
else
{
if (balance> = 0)
{
if (right! = NULL)
{
AvlTree <KEY, VALUE> * tNode = right;
while (tNode-> left! = NULL)
{
tNode = tNode-> left;
}
KEY tKey = key;
VALUE tValue = value;
key = tNode-> key;
value = tNode-> value;
tNode-> key = tKey;
tNode-> value = tValue;
balance -= right-> remove (Key, this);
}
}
else
{
if (left! = NULL)
{
AvlTree <KEY, VALUE> * tNode = left;
while (tNode-> right! = NULL)
{
tNode = tNode-> right;
}
KEY tKey = key;
VALUE tValue = value;
key = tNode-> key;
value = tNode-> value;
tNode-> key = tKey;
tNode-> value = tValue;
balance + = left-> remove (Key, this);
}
}
}
}
else
{
if (Key> key)
{
if (right! = NULL)
{
balance -= right-> remove (Key, this);
TurnAround ();
}
else
{
throw CString ("Не знайдено ");
}
}
else
{
if (left! = NULL)
{
balance + = left-> remove (Key, this);
TurnAround ();
}
else
{
throw CString ("Не знайдено ");
}
}
}
if (balance! = a)
{
return (balance == 0)? (1): (0);
}
else
{
return 0;
}
}
~ AvlTree ()
{
}
};
СПИСОК ЛІТЕРАТУРИ
1. Карран Ф.М., Прічард Дж.Дж. К26 Абстракція даних і рішення завдань на С + + - I -. Стіни і дзеркала, 3-е видання.: Пер.с англ. - М.: Видавничий дім «Вільямс», 2003. - 848 с: іл. - Хрон. тит. англ.
2. Ж.-Л. Лорьер. Системи штучного інтелекту. - М.: Світ, 1991.
3. Бабе Б. Просто і ясно про Borland С + +: пров. з англ. - СПб.: Пітер, 1997. - 464 с.
4. ІРЕ П. Об'єктно - орієнтоване програмування з використанням С + +: пров. з англ. К.: НІПФ ДіаСофтЛтд, 1995. - 480 с.
5. Програмування. Підручник під ред. Свердлик О.М., МО СРСР, 1992. - 608 с.
6. Сван Т. Програмування для Windows в Borland С + +: пров. з англ. - М.: БІНОМ. - 480 с.
7. Шаміс В. О. Borland С + + Builder. Програмування на С + + без проблем. - М.: Нолидж, 1997. - 266 с.
8. Шілдт Г. Теорія і практика С + +: пров. з англ. - СПб.: BHV - Санкт - Петербург, 1996. - 416 с.
9. http://www.rsdn.ru/article/alg/bintree/avl.xml.